1. Field of the Invention
The present invention relates to object layouts and, more particularly, to a system and method for correcting design rule violations for object layouts in very large scale integrated (VLSI) circuits.
2. Description of the Related Art
Semiconductor chip layout is subject to complex rules governing, among other things, geometry of shapes on process layers. These complex rules may include, for example, width requirements, spacing requirements, overlap requirements, etc. Compliance with these rules, called design rules, is important to chip functionality and manufacturability.
Many conventional processes used to create or alter layouts can introduce design rule violations. Manual layout, for example, inevitably introduces violations due to the difficulty of satisfying a large number of complex design rules by hand. These violations are generally corrected via tedious iterations between design rule checking tool runs and manual layout modifications.
Technology migration is another process which gives rise to a very large number of design rule violations. Migration is the process which transforms layouts in one technology to a layout in a technology with different design rules. The migration process begins with a simple scaling, using commercially available programs, and is sufficient to produce a design-rule-correct layout. In many cases, however, non-scalable differences in the design rules result in the introduction of design rules violations, which must again be corrected by hand by tedious manual iteration.
To date, the only automation technology available to assist in design rule violation correction is compaction. Compaction is a technique used to minimize the area of a layout while satisfying design rules. Design rule violation correction is accomplished as a side effect of the process. The prime objective of minimizing area can cause great disruption to the layout. Critical alignments, inter-net spacing, symmetries, power, performance, etc. can be easily lost in the process. Designers generally find this degree of disruption unacceptable. Though some of the critical features may be preserved by the addition of manual constraints. Adding these constraints is another tedious, error prone process. As a consequence of these limitations, compaction has not found wide use as a design rule correction aid.
Compaction is performed as follows. Compaction includes two steps. The first step includes constraint graph generation and the second includes constrained optimization. Conventional compaction modifies a layout in one direction at a time. For simplicity, compaction is described for a horizontal direction (or x direction in Cartesian coordinates) modification. The same method applies for a vertical direction (or y direction in Cartesian coordinates).
The linear constraints are established which represent the separation between layout elements required by design rules. A constraint based optimization is performed based on a selected objective function which is subject to the system of linear constraints. In conventional compaction, the objective function is a minimum sum of all X.sub.i, where X.sub.i is a variable representing the position of an element, subject to the system of linear constraints. Conventional compaction also includes aspects, for example wire length minimization. Further details of compaction are contained in an article by Liao et al. entitled "An Algorithm to Compact a VLSI Symbolic Layout with Mixed Constraints", 20th Design Automation Conference, Miami Beach, Fla., June 1983, pp. 107-112 and an article by Lee et al. entitled "A Performance-Aimed Cell Compactor with Automatic Jogs", IEEE Transaction on Computer Aided Design, VOL. 11, No. 12, December 1992, pp. 1495-1507.
Minimizing the sum of X.sub.i 's has the effect of selecting the smallest value of X.sub.i for each edge in the design. This is equivalent to pushing all edges in the design as far to one side as possible which also minimizes area which is unacceptable. Together with a wire length objective, the conventional compaction produces more reasonable results. However, this global minimization often comes with unacceptable perturbation of the original layout.
Therefore, a need exists for a system and method for automatically correcting design rule violations with minimal disruption to the input layout. A further need exists for a system and method for automatically correcting design rule violations during technology migration.